
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicReferenceArray;


public class OptWFQueue implements Queue { 
	
	public class Node {
		public int value;
		public AtomicReference<Node> next;
		public int enqTid;
		public AtomicInteger deqTid;
		public Node (int val, int etid) {
			value = val;
			next = new AtomicReference<Node>(null);
			enqTid = etid;       
			deqTid = new AtomicInteger(-1);                         
		}		
	}

	protected class OpDesc {
		public long phase;
		public boolean pending;
		public boolean enqueue;
		public Node node;
		public OpDesc (long ph, boolean pend, boolean enq, Node n) {
			phase = ph;
			pending = pend;
			enqueue = enq;
			node = n;
		}
	}
	
	protected AtomicReference<Node> head, tail;
	protected AtomicReferenceArray<OpDesc> state;

	int nextToHelp[];
	AtomicInteger maxPhaseCnt = new AtomicInteger(0);

	public OptWFQueue () {
		Node sentinel = new Node(-1, -1);
		head = new AtomicReference<Node>(sentinel);
		tail = new AtomicReference<Node>(sentinel);
		
		state = new AtomicReferenceArray<OpDesc>(Test.numThreads);
		nextToHelp = new int[state.length()];
    
    for (int i = 0; i < state.length(); i++) {
      state.set(i, new OpDesc(-1, false, true, null));
			
			nextToHelp[i] = i + 1;
		}
		
	}

	public void enq(int tid, int value) {
		long phase = maxPhase() + 1;
		state.set(tid, new OpDesc(phase, true, true, new Node(value, tid)));
		help(tid, phase, true);
		help_finish_enq();
	}


	public int deq(int tid) throws Exception {
		long phase = maxPhase() + 1;
		state.set(tid, new OpDesc(phase, true, false, null));
		help(tid, phase, false);
		help_finish_deq();

		Node node = state.get(tid).node;
		
		if (node == null) {
			throw new Exception();
		}   
		
    return node.next.get().value;  
	}
	
	protected void help(int tid, long phase, boolean enqueue) {
		int tidToHelp = (nextToHelp[tid]++) % nextToHelp.length;
		if (tidToHelp != tid) {
			OpDesc desc = state.get(tidToHelp);                        
			if (desc.pending && desc.phase <= phase) {
				if (desc.enqueue) {
					help_enq(tidToHelp, phase);
				} else {
					help_deq(tidToHelp, phase);
				}
			}		 
		}
		if (enqueue) {
			help_enq(tid, phase);
		} else {
			help_deq(tid, phase);
		}		
	}
	
	
	protected void help_enq(int tid, long phase) {
		while (isStillPending(tid, phase)) {
			Node last = tail.get();
			Node next = last.next.get();
			if (last == tail.get()) {
				if (next == null) {
					if (isStillPending(tid, phase)) {  
						if (last.next.compareAndSet(next, state.get(tid).node)) {							
							help_finish_enq();
							return;
						}
					}
				} else {
					help_finish_enq();					
				}
			} 
		}
	}

	protected void help_finish_enq() {
		Node last = tail.get();
		Node next = last.next.get();
		if (next != null) {
			int tid = next.enqTid;
			OpDesc curDesc = state.get(tid);
			if (last == tail.get() && state.get(tid).node == next) {
				OpDesc newDesc = new OpDesc(state.get(tid).phase, false, true, next);
				state.compareAndSet(tid, curDesc, newDesc);
				tail.compareAndSet(last, next);				
			}
		}
	}
	
	protected void help_deq(int tid, long phase) {
 		while (isStillPending(tid, phase)) {
			Node first = head.get();                                  
			Node last = tail.get();                                   
			Node next = first.next.get();                             		
			if (first == head.get()) {
				if (first == last) {
					if (next == null) {
						OpDesc curDesc = state.get(tid);
						if (last == tail.get() && isStillPending(tid, phase)) {
							OpDesc newDesc = new OpDesc(state.get(tid).phase, false, false, null);  
 							state.compareAndSet(tid, curDesc, newDesc);
						}
					} else {
						help_finish_enq();
					}				
				} else { 				
					OpDesc curDesc = state.get(tid);
					Node node = curDesc.node;
					if (!isStillPending(tid, phase)) break;
					if (first == head.get() && node != first) {
						OpDesc newDesc = new OpDesc(state.get(tid).phase, true, false, first);  
						if (!state.compareAndSet(tid, curDesc, newDesc)) {
							continue;
						}
					}
					first.deqTid.compareAndSet(-1, tid);
					help_finish_deq();
				}
			}
 		}
	}
	
	protected void help_finish_deq()  {
		Node first = head.get();                                  
		Node next = first.next.get();
		int tid = first.deqTid.get();
		if (tid != -1) {
			OpDesc curDesc = state.get(tid);
			if (first == head.get() && next != null) {
				OpDesc newDesc = new OpDesc(state.get(tid).phase, false, false, state.get(tid).node);  
				state.compareAndSet(tid, curDesc, newDesc);
				head.compareAndSet(first, next);
			}
		}
	}

	protected long maxPhase() {
    int phase = maxPhaseCnt.get(); 
    maxPhaseCnt.compareAndSet(phase, phase + 1);
    return phase;
/*		long maxPhase = -1;
		for (int i = 0; i < state.length(); i++) {
			long phase = state.get(i).phase;
			if (phase > maxPhase) {
				maxPhase = phase;
			}
		}
		return maxPhase;
*/	}
	
	protected boolean isStillPending(int tid, long ph) {
	  // it can be done this way, but we stay consistent with non-optimized impl.
    //   OpDesc desc = state.get(tid);
    //   return desc.pending && desc.phase <= ph;
	
	  return state.get(tid).pending && 
      state.get(tid).phase <= ph;
	}

}